package com.dq.offer;

import java.util.PriorityQueue;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/14  22:30
 * @Description:
 */
public class NumberOverHalf {

    public static void main(String[] args) {
        NumberOverHalf s = new NumberOverHalf();

        int[] nums = {47,47,72,47,72,47,79,47,12,92,13,47,47,83,33,15,18,47,47,47,47,64,
                47,65,47,47,47,47,70,47,47,55,47,47,47,46,30,58,59,47,47,
                47,47,47,90,64,37,20,47,100,84,47,47,47,89,47,36,47,60,
                47,47,47,47,47,22,47,54,30,11,47,47,86,49,34,19,67,16,47,36,47,47};
        System.out.println(nums.length/2);
        System.out.println(s.partation(nums, 0, nums.length-1, nums.length/2));
    }
    private int partation(int[] nums, int low, int hight, int target){

        int k = nums[low];
        int left = low+1, right = low + 1;
        while(right <= hight){
            int t = nums[right++];
            if(t <= k){
                swap(nums, left, right-1);
                left++;
            }
        }

        swap(nums, low, --left);
        if(left == target) return k;
        if(left < target) return partation(nums, left+1, hight, target);
        else return partation(nums, low, left-1, target);
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
